package com.mashibing.class12;

// 判断一棵树是否是二叉搜索树.

/**
 * 判断是否是二叉搜索树:
 * 1) 左子树的最大值 小于或等于当前节点的值
 * 2) 右子树的最小值 大于或等于当前节点的值.
 */
public class Code02_IsBST {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static class Info{
        public boolean isBST;
        public int max;
        public int min;

        public Info(boolean isBST, int max, int min) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }
    }

    public static boolean isBST(Node node){
        return process(node).isBST;
    }

    public static Info process(Node node){
        if (node == null){
            return null;
        }
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        int max = node.value;
        int min = node.value;
        if (leftInfo!=null){
            max = Math.max(max,leftInfo.max);
            min = Math.min(min,leftInfo.min);
        }
        if (rightInfo!=null){
            max = Math.max(max, rightInfo.max);
            min = Math.min(min, rightInfo.min);
        }
        boolean isBST = true;
        if (leftInfo!=null && !leftInfo.isBST){
            isBST = false;
        }
        if (rightInfo!=null && !rightInfo.isBST){
            isBST = false;
        }
        if (leftInfo!=null && leftInfo.max >= node.value){
            isBST = false;
        }
        if (rightInfo!=null && rightInfo.min <= node.value){
            isBST = false;
        }
        return new Info(isBST,max,min);
    }
}
